/*
 * Na šachovnici P (obdelnikovou sit m * k) je pevně rozmístěno f bodů.
 * Úkolem je rozmístit dalších b-f bodů, tak aby byl maximální součet matice
 * Euklidovských vzdáleností všech dvojic bodů = sum_i_j d(i,j). Body se nesmějí
 * překrývat.
 *
 * Geometrická interpretace: rozmístit na ploše b bodů tak, aby byly co nejdál
 * od sebe.
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "main.h"
#include "io.h"
#include "state.h"
#include "stack.h"
#include "plane.h"
#include "util.h"

#define INPUT_FILE_PATH "./input.txt"

void doWork(void);
void processState(State *state);
void generateChildren(State *state);

/* Nejlepší dosavadní řešení */
State *bestState;
double bestValue = -1;

/* unsigned long long int je zoufale málo pro tyto potřeby */

/* unsigned long long int combinations;
unsigned long long int progress = 0;
int percents = 0; */

/*
 * Hlavní funkce programu.
 */
int main(int argc, char **argv) {
	/* nulové buffery pro výstup --> pro ladění při segfaultech */
    setvbuf(stdout, NULL, _IONBF, 0);
    setvbuf(stderr, NULL, _IONBF, 0);

	printf("Vítejte v programu nenávist!\n");

	/* otevřeme soubor se vstupními daty */
    FILE *inputFile = fopen(INPUT_FILE_PATH, "r");
    if(inputFile == NULL){
    	fprintf(stderr, "ERROR READING INPUT FILE %s\n", INPUT_FILE_PATH);
    	return EXIT_FAILURE;
    }

    /* načteme vstupní data */
    loadInput(inputFile);

    /* validace vstupních dat */
    if(b > m*k){
    	fprintf(stderr, "Je specifikováno více bodů, než se na plán může vejít (%d > %d*%d)\n", b, m, k);
    	return EXIT_FAILURE;
    }
    if(b < f){
    	fprintf(stderr, "Počet pevně umístěných bodů je větší než celkový počet bodů: (b < f, %d < %d). Nelze umístit záporný počet bodů.\n", b, f);
    	return EXIT_FAILURE;
    }
	int i;
    for(i = 0; i < f; i++){
    	if(fixedPoints[i].x >= m || fixedPoints[i].y >= k){
        	fprintf(stderr, "Jedna souřadnice je specifikována mimo plán ([%d, %d])\n", fixedPoints[i].x, fixedPoints[i].y);
        	return EXIT_FAILURE;
    	}
    }

    /* int N = m*k - f, K = b - f;
    combinations = fact(N)/(fact(K)*fact(N - K)); */

    /* výpis vstupních dat */
	printf("Vstupní data: m = %d, k = %d, f = %d, b = %d.\n", m, k, f, b);
	for(i = 0; i < f; i++){
		printf("%d: [%d,%d] ", i, fixedPoints[i].x, fixedPoints[i].y);
	}
	printf("\n");
    /* printf("Počet kombinací: %d", combinations); */

	/* Zadání počátečního stavu */
	stackPush(allocateState(0));

	clock_t start = clock();
	/* Spuštění práce */
	doWork();

	clock_t end = clock();

	printf("Celkový čas: %f s", ((double) (end - start)) / CLOCKS_PER_SEC);

	return 0;
}

/*
 * Pracovní metoda programu s hlavním cyklem, který má na zodpovědnost zpracovat
 * všechny stavy. Po skončení vypíše nejlepší řešení.
 */
void doWork(void){
	State *state;

	while((state = stackPop()) != NULL){
		processState(state);
	}

	printf("BEST SOLUTION:\n");
	printPlane(bestState);
	printState(bestState);
	printf("Solution value: %f\n", bestValue);
}

/*
 * Metoda zpracuje stav - buď spočítá jeho hodnotu (pro konečné stavy) nebo
 * vygeneruje potomky.
 */
void processState(State *state){
	/*printf("--------------------\n");
	printPlane(state);
	printState(state);*/

	/* Pro stavy na konečné hloubce - listy */
	if(state->depth == b - f){
		double result = state->value;
		/* printf("Result is: %f\n", result); */
		if(result > bestValue){
			bestValue = result;
			bestState = state;
		}
		else{
			freeState(state);
		}
		/*progress++;
		if(100 * progress / combinations > percents){
			percents = 100 * progress / combinations;
			//printf("%d%%\n", percents);
		}*/
	}
	/* Pro stavy ve stromu - větve */
	else{
		generateChildren(state);
		freeState(state);
	}
}

/*
 * Pro zadaný stav vygeneruje potomky a vloží je do stacku.
 */
void generateChildren(State *state) {
	/*
	 * Optimalizace --> z permutací na kombinace.
	 */
	int lastPointX = 0, lastPointY = 0;
	int i;
	for(i = 0; i < state->depth; i++){
		if(lastPointX < state->statePoints[i].x){
			lastPointX = state->statePoints[i].x;
			lastPointY = state->statePoints[i].y;
		}
		else if(lastPointX == state->statePoints[i].x){
			lastPointY = max(lastPointY, state->statePoints[i].y);
		}
	}
	/*
	 * hasPoint - proměnná, která určuje, zda-li je na aktuálních souřadnicích
	 * už bod umístěn (buď fixní nebo umístěný).
	 */
	int j, l, hasPoint;
	for(i = lastPointX; i < m; i++){
		for(j = 0; j < k; j++){
			if(j == 0 && i == lastPointX){
				j = lastPointY;
			}
			hasPoint = 0;
			/* prohledáváme fixní body */
			for(l = 0; l < f; l++){
				if(fixedPoints[l].x == i && fixedPoints[l].y == j){
					hasPoint = 1;
					break;
				}
			}
			if(hasPoint){
				continue;
			}
			/* prohledáváme již umístěné body */
			for(l = 0; l < state->depth; l++){
				if(state->statePoints[l].x == i && state->statePoints[l].y == j){
					hasPoint = 1;
					break;
				}
			}
			if(hasPoint){
				continue;
			}
			State *newState = childState(state, i, j);
			stackPush(newState);
		}
	}
}
